import java.lang.reflect.Array;

//归并排序
class Solution {
    public int[] sortArray(int[] nums) {
        mergeSorr(nums,0,nums.length-1);
        return nums;
    }
    public void mergeSorr(int[] nums, int left, int right) {
        if(left>=right) return;

        //1.根据中间点划分区间
        int mid = (left+right)/2;
        //[left,mid] [mid+1,right]

        //2.把左右区间排个序
        mergeSorr(nums,left,mid);
        mergeSorr(nums,mid+1,right);

        //3.合并两个有序数组
        int[] tmp = new int[right-left+1];
        int cur1 = left,cur2 = mid+1,i=0;
        while(cur1<=mid&&cur2<=right) {
            if(nums[cur1]<=nums[cur2]) {
                tmp[i++] = nums[cur1++];
            }else {
                tmp[i++] = nums[cur2++];
            }
        }
        //处理没有遍历的数组
        while(cur1<=mid) {
            tmp[i++] = nums[cur1++];
        }
        while(cur2<=right) {
            tmp[i++] = nums[cur2++];
        }

        //还原
        for (int j = left; j<=right; j++) {
            nums[j] = tmp[j-left];
        }
    }
}
public class Test {
}
